package com.lzhsite.leetcode.algoritom.practise.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/*
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
 ["ate","eat","tea"],
 ["nat","tan"],
 ["bat"]
]
*/

public class 字母异位词分组 {

	public List<List<String>> groupAnagrams(String[] strs) {

		Map<String, List<String>> map = new HashMap<>();
		for (int i = 0; i < strs.length; i++) {
			char[] s = strs[i].toCharArray();
			Arrays.sort(s);
			StringBuffer key = new StringBuffer();
			for (char c : s) {
				key.append(c);
			}
			String mykey = key.toString();
			if (map.containsKey(mykey)) {
			   map.get(mykey).add(strs[i]);
			} else {
				List list = new ArrayList<>();
				list.add(strs[i]);
				map.put(mykey, list);
			}
		}
 

		 return new ArrayList<List<String>>(map.values());
	}

 
	//
	// 空间复杂度：O（NK）O（NK） 
	// 首先初始化 key = "0#0#0#0#0#"，数字分别代表 abcde 出现的次数，# 用来分割。
	// 这样的话，"abb" 就映射到了 "1#2#0#0#0"。
	// "cdc" 就映射到了 "0#0#2#1#0"。
	// "dcc" 就映射到了 "0#0#2#1#0"。

	public List<List<String>> groupAnagrams2(String[] strs) {
		HashMap<String, List<String>> hash = new HashMap<>();
		for (int i = 0; i < strs.length; i++) {
			int[] num = new int[26];
			// 记录每个字符的次数
			for (int j = 0; j < strs[i].length(); j++) {
				num[strs[i].charAt(j) - 'a']++;
			}
			// 转成 0#2#2# 类似的形式
			String key = "";
			for (int j = 0; j < num.length; j++) {
				key = key + num[j] + '#';
			}
			if (hash.containsKey(key)) {
				hash.get(key).add(strs[i]);
			} else {
				List<String> temp = new ArrayList<String>();
				temp.add(strs[i]);
				hash.put(key, temp);
			}

		}
		return new ArrayList<List<String>>(hash.values());
	}
	
	
	
//	算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。
//	利用这个，我们把每个字符串都映射到一个正数上。
//	用一个数组存储质数 prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}。
//	然后每个字符串的字符减去 ' a ' ，然后取到 prime 中对应的质数。把它们累乘。
//	例如 abc ，就对应 'a' - 'a'， 'b' - 'a'， 'c' - 'a'，即 0, 1, 2，也就是对应素数 2 3 5，然后相乘 2 * 3 * 5 = 30，就把 "abc" 映射到了 30。

	public List<List<String>> groupAnagrams3(String[] strs) {
	    HashMap<Integer, List<String>> hash = new HashMap<>();
	    //每个字母对应一个质数
	    int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 };
	    for (int i = 0; i < strs.length; i++) {
	        int key = 1;
	        //累乘得到 key
	        for (int j = 0; j < strs[i].length(); j++) {
	            key *= prime[strs[i].charAt(j) - 'a'];
	        } 
	        if (hash.containsKey(key)) {
	            hash.get(key).add(strs[i]);
	        } else {
	            List<String> temp = new ArrayList<String>();
	            temp.add(strs[i]);
	            hash.put(key, temp);
	        }

	    }
	    return new ArrayList<List<String>>(hash.values());
	}
 

	public static void main(String[] args) {
		String[] a = { "eat", "tea", "tan", "ate", "nat", "bat" };
		new 字母异位词分组().groupAnagrams(a);
	}
}
